package com.moyoutian.leetcode;

/**
 * 29. 两数相除
 * 给定两个整数，被除数dividend和除数divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
 * <p>
 * 返回被除数dividend除以除数divisor得到的商。
 * <p>
 * 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
 * <p>
 * <p>
 * <p>
 * 示例1:
 * <p>
 * 输入: dividend = 10, divisor = 3
 * 输出: 3
 * 解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
 * 示例2:
 * <p>
 * 输入: dividend = 7, divisor = -3
 * 输出: -2
 * 解释: 7/-3 = truncate(-2.33333..) = -2
 * <p>
 * <p>
 * 提示：
 * <p>
 * 被除数和除数均为 32 位有符号整数。
 * 除数不为0。
 * 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231− 1]。本题中，如果除法结果溢出，则返回 231− 1。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/divide-two-integers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Demo29 {
    public static void main(String[] args) {
        System.out.println(divide(-2147483648, 1));
    }

    /**
     * 给定两个整数，被除数dividend和除数divisor。将两数相除，要求不使用乘法、除法和 mod 运算符
     *
     * @param dividend
     * @param divisor
     * @return
     */
    public static int divide(int dividend, int divisor) {
        //不能用除法肯定是减法来实现
        //关键是怎样快速（高效）的减
        //符号处理，-最小值转换成最大值会减少1所以这里先转换成long值处理
        if (dividend == 0) {
            return 0;
        }
        long tempDividend = dividend;
        long tempDivisor = divisor;

        tempDividend = tempDividend > 0 ? tempDividend : -tempDividend;
        tempDivisor = tempDivisor > 0 ? tempDivisor : -tempDivisor;
        long temp = substruction(tempDividend, tempDivisor);
        //符号处理
        if ((dividend > 0 && divisor > 0 || dividend < 0 && divisor < 0)) {
            return temp > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) temp;
        } else {
            return -temp < Integer.MIN_VALUE ? Integer.MIN_VALUE : (int) -temp;
        }
    }


    /**
     * 思路1直接减法
     */
    public static long substruction1(long dividend, long divisor) {
        //不能用除法肯定是减法来实现
        //关键是怎样快速（高效）的减
        //思路1直接减法
        long count = 0;
        while (dividend >= divisor) {
            dividend = dividend - divisor;
            count++;
        }
        return count > Integer.MAX_VALUE ? Integer.MAX_VALUE : count;
    }

    /**
     * 思路2减去一个除数的倍数的数
     */
    public static long substruction(long dividend, long divisor) {
        //不能用除法肯定是减法来实现
        //关键是怎样快速（高效）的减
        //减去一个除数的倍数的数
        long count = 0;
        // 算出一个最大的位运算的可减数
        if (dividend >= divisor) {
            long temp = divisor;
            count = 1;
            while (dividend >= temp << 1) {
                temp = temp << 1;
                count = count << 1;
            }
            if (dividend - temp >= divisor) {
                count = count + substruction(dividend - temp, divisor);
            }
        }
        return count;
    }

}
